package DFSandBFS;
import java.util.*;
/**
 * 计算二叉树中路径和等于目标值的路径数量
 * 时间复杂度O(n)，空间复杂度O(h)，n为节点个数，h为树的高度
 */
public class pathSum {
    /**
     * 二叉树节点类
     * 包含节点值、左子节点和右子节点
     */
    public static class TreeNode{
        int val;            // 节点值
        TreeNode left;      // 左子节点
        TreeNode right;     // 右子节点
        
        // 无参构造函数
        TreeNode(){}
        
        // 带值的构造函数
        TreeNode(int val){
            this.val = val;
        }
        
        // 带值、左子节点和右子节点的构造函数
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 计算二叉树中路径和等于目标值的路径数量
     * 
     * @param root 二叉树的根节点
     * @param targetSum 目标路径和
     * @return 路径和等于目标值的路径数量
     */
    public static int pathSumM(TreeNode root, int targetSum){
        if(root == null) return 0; // 如果根节点为空，返回0
        dfs(root, targetSum, 0L); // 调用深度优先搜索方法计算路径和
        pathSumM(root.left, targetSum); // 递归计算左子树的路径和
        pathSumM(root.right, targetSum); // 递归计算右子树的路径和
        return num; // 返回路径和等于目标值的路径数量
    }

    static int num; // 用于存储路径和等于目标值的路径数量

    /**
     * 深度优先搜索方法，用于计算路径和
     * 
     * @param root 当前节点
     * @param targetSum 目标路径和
     * @param sum 当前路径和
     */
    public static void dfs(TreeNode root, int targetSum, long sum){
        if(root == null) return; // 如果当前节点为空，返回
        sum += root.val; // 更新当前路径和
        if(sum == targetSum) num++; // 如果当前路径和等于目标值，路径数量加1
        dfs(root.left, targetSum, sum); // 递归计算左子树的路径和
        dfs(root.right, targetSum, sum); // 递归计算右子树的路径和
    }
    // ------------------------------------------------------------------------------------------------------------
    // 主方法pathSUm中递归子树的时候存在重复计算过程
    // 如果存在一条路径以root.left为起点，从根节点开始的递归中就无法找到该路径
    // 通过哈希表记录所有从root开始的路径和，就可以在从根节点开始的递归中，通过
    // map.get(sum - gergetSum)找到该路径，因为只需要统计路径数量，满足该条件就证明存在这样一条路径
    // num += map.getOrDefault(sum - targetSum, 0)就可以更新路径数量
    // 进递归时，保存root到当前节点的路径和，map.put(sum, map.getOrDefault(sum, 0) + 1)
    // 若路径和已经存在则+1，不存在则创建路径和，进行递归左右子树
    // dfs(root.left, targetSum, sum)
    // dfs(root.right, targetSum, sum)
    // 递归终止后需要进行回溯，恢复之前的状态，避免影响其他路径的遍历
    // map.put(sum, map.get(sum) - 1)
    // ------------------------------------------------------------------------------------------------------------
    /**
     * 计算二叉树中路径和等于目标值的路径数量（使用哈希表优化）
     * 
     * @param root 二叉树的根节点
     * @param targetSum 目标路径和
     * @return 路径和等于目标值的路径数量
     */
    public static int pathSum2(TreeNode root, int targetSum){
        if(root == null) return 0; // 如果根节点为空，返回0
        map.put(0L, 1); // 初始化哈希表，表示路径和为0的路径数量为1
        dfs(root, targetSum, 0L); // 调用深度优先搜索方法计算路径和
        return num2; // 返回路径和等于目标值的路径数量
    }

    static int num2; // 用于存储路径和等于目标值的路径数量
    static HashMap<Long, Integer> map = new HashMap<>(); // 哈希表，用于存储路径和及其出现次数

    /**
     * 深度优先搜索方法，用于计算路径和（使用哈希表优化）
     * 
     * @param root 当前节点
     * @param targetSum 目标路径和
     * @param sum 当前路径和
     */
    public static void dfs2(TreeNode root, int targetSum, long sum){
        if(root == null) return; // 如果当前节点为空，返回
        sum += root.val; // 更新当前路径和
        num2 += map.getOrDefault(sum - targetSum, 0); // 累加路径和等于目标值的路径数量
        map.put(sum, map.getOrDefault(sum, 0) + 1); // 更新哈希表，增加当前路径和的出现次数
        dfs2(root.left, targetSum, sum); // 递归计算左子树的路径和
        dfs2(root.right, targetSum, sum); // 递归计算右子树的路径和
        map.put(sum, map.get(sum) - 1); // 恢复哈希表，减少当前路径和的出现次数
    }
    // ------------------------------------------------------------------------------------------------------------
    /**
     * 根据层序遍历的字符串数组构建二叉树
     * 
     * @param nodes 层序遍历的节点值数组，"null"表示空节点
     * @return 构建好的二叉树根节点
     */
    public static TreeNode buildTree(String[] nodes){
        if(nodes == null || nodes.length == 0 || nodes[0].equals("null")) // 如果输入数组为空或根节点为null
            return null; // 返回null
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0])); // 创建根节点
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root); // 将根节点加入队列
        int index = 1; // 从第二个节点开始处理
        while(!queue.isEmpty() && index < nodes.length){ // 当队列不为空且未处理完所有节点时，继续构建
            TreeNode cur = queue.poll(); // 取出队首节点
            if(index < nodes.length && !nodes[index].equals("null")){ // 如果左子节点不为null
                cur.left = new TreeNode(Integer.parseInt(nodes[index])); // 创建左子节点
                queue.offer(cur.left); // 将左子节点加入队列
            }
            index++; // 处理下一个节点
            if(index < nodes.length && !nodes[index].equals("null")){ // 如果右子节点不为null
                cur.right = new TreeNode(Integer.parseInt(nodes[index])); // 创建右子节点
                queue.offer(cur.right); // 将右子节点加入队列
            }
            index++; // 处理下一个节点
        }
        return root; // 返回构建好的二叉树根节点
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示二叉树的层序遍历，"null"表示空节点
     * 例如：1,2,3,null,null,4,5 表示一个二叉树
     * 输出格式：路径和等于目标值的路径数量
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nodes = sc.nextLine().split(","); // 读取输入并分割
        int targetSum = sc.nextInt(); // 读取目标路径和
        TreeNode root = buildTree(nodes); // 构建二叉树
        int result = pathSumM(root, targetSum); // 计算路径和等于目标值的路径数量
        System.out.println(result); // 输出结果
        sc.close(); // 关闭输入流
    }
}
